package com.hy.treeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class NTreeNodeLevelOrder {


    /**
     * 429.N叉树的层序遍历
     * 力扣题目链接
     *
     * 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
     *
     * 思路:
     *
     * 这道题依旧是模板题，只不过一个节点有多个孩子了
     *
     */
    // N
    public List<List<Integer>> levelOrder(NTreeNode root){
        List<List<Integer>> res = new ArrayList<>();
        Deque<NTreeNode> deque = new LinkedList<>();
        if (root == null){
            return res;
        }
        deque.offerLast(root);

        while (!deque.isEmpty()){
            int len = deque.size();
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                NTreeNode node = deque.pollFirst();
                temp.add(node.val);
                List<NTreeNode> child = node.child;
                if (child == null || child.size() == 0){
                    continue;
                }
                for (NTreeNode c : child) {
                    if (c != null){
                        deque.offerLast(c);
                    }
                }

            }
            res.add(temp);
        }
        return res;
    }



    public static void main(String[] args) {
        NTreeNode leftNode1 = new NTreeNode(1, null);
        NTreeNode rightNode1 = new NTreeNode(2, null);

        NTreeNode leftNode2 = new NTreeNode(6, null);
        NTreeNode rightNode2 = new NTreeNode(8, null);

        List<NTreeNode> child1 = new ArrayList<>();
        child1.add(leftNode1);
        child1.add(rightNode1);
        List<NTreeNode> child2 = new ArrayList<>();
        child2.add(leftNode2);
        child2.add(rightNode2);
        NTreeNode leftNode = new NTreeNode(4, child1);
        NTreeNode rightNode = new NTreeNode(7, child2);

        List<NTreeNode> child = new ArrayList<>();
        child.add(leftNode);
        child.add(rightNode);

        NTreeNode root = new NTreeNode(5, child);
        NTreeNodeLevelOrder nTreeNodeLevelOrder = new NTreeNodeLevelOrder();
        System.out.println("多叉树-层序遍历： "+nTreeNodeLevelOrder.levelOrder(root));

    }
}
